<?php
//This Code is published under the conditions of the CDDL (Sun Microsystems) (c) 2008 by Fabian Tschirschnitz
//Diese Klasse beinhaltet Funktionen zum Erstellen von paarweisen Alignments
//SequenceALignmentSearchingApproach
	class SALSA{
	//Klassenattribute
	//Sequenzstrings
	private $seq1;
	private $seq2;
	//Sequenz_ID's
	private $seq1_id;
	private $seq2_id;
	//längere Sequenzlänge
	private $longer;
	//Alignment-Matrix
	private $matrix;
		//Konstruktor
		function __construct($seq1, $seq2){
		   //Strings bereinigen von Whitspaces und Zahlen
			$this->seq1 = str_replace(array("\n", "\r", "\t", " ", "\o", "\xOB"), '', $seq1->getseq());
			$this->seq2 = str_replace(array("\n", "\r", "\t", " ", "\o", "\xOB"), '', $seq2->getseq());
			$this->seq1 = preg_replace("/\W\d/","",$this->seq1);
			$this->seq2 = preg_replace("/\W\d/","",$this->seq2);
			//nötige Speicherlimitierung, hier für php.ini: memory_limit=32M
			$this->seq1 = substr($this->seq1,0,380);
			$this->seq2 = substr($this->seq2,0,380);
			//Maximallänge bestimmen
			$this->longer = max(sizeof($this->seq1), sizeof($this->seq2));}
		//Dotplot erstellen	
		function get_dotplot($ktpl=3){
		  //Matrix initialiesieren und Größe ermitteln
		  $a = str_split($this->seq1, 1);
        $b = str_split($this->seq2, 1);
        $maxa=sizeof($a);
        $maxb=sizeof($b);
	     //Matrix füllen
        for ($i=0;$i<$maxa;$i++){
                for ($j=0;$j<$maxb;$j++){
                        	if($b[$j]==$a[$i]){
                                $matrix[$i][$j]=1;
                        	}else{
                                $matrix[$i][$j]=0;
                        	}       
                }
         }
		   //Wortmethode als Filter durchläuft Matrix ein zweites Mal und filtert Rauschen
			for ($i=0;$i<$maxa;$i++){
                for ($j=0;$j<$maxb;$j++){
                			//nachfolgende Elemente bis zu einer Tiefe von $ktpl kontrollieren: nur 1, wenn $matrix[$i+1][$j+1]!=0
                        for($k=1;$k<$ktpl;$k++){
                        	if($matrix[$i][$j]!=0 && $matrix[$i+$k][$j+$k]!=0){
                                $matrix[$i][$j]=1;
                           //Verhinderung des "Abhackens" der letzten Alignment-Treffer durch Überprufung des Wertes: $matrix[$i-1][$j-1] 
                        	}else{
                        		if($matrix[$i][$j]!=0 && $matrix[$i-1][$j-1]!=0){$matrix[$i][$j]=1;break;}
                              $matrix[$i][$j]=0;
                        	}
                        }       
                }
        	}
        return $matrix;
      }
      
      function get_levenshtein(){
         $a = " ".$this->seq1;
       	$b = " ".$this->seq2;
       	
       	//Matrix initialiesieren
			for ($i=0; $i<=strlen($a); $i++)
            $matrix[$i][0] = $i;
       	for ($j=0; $j<=strlen($b); $j++)
            $matrix[0][$j] = $j;
       	
         //Matrix durchlaufen      	
  			for($i = 1; $i <= strlen($a); $i++){
    			for($j = 1; $j <= strlen($b); $j++){
    				//ist Präfix ein Match cost=0, sonst cost=1
      			if($a[$i - 1] == $b[$j - 1])
       				 $cost = 0; else $cost = 1;
      			 	 $matrix[$i][$j] = min($matrix[$i - 1][$j] + 1, $matrix[$i][$j - 1] + 1, $matrix[$i - 1][$j - 1] + $cost);
      			 	 //Speichertrick
      			 	 unset($matrix[$i-2][$j-2]);      			
    			}
    		}
  		return $matrix[strlen($a)][strlen($b)];
      }
	
	
	}
?>